﻿package kizzo.datastruct   
{			
	import flash.display.Sprite;
	import flash.events.EventDispatcher;	
	import flash.net.URLLoader;
	import flash.net.URLRequest;
	import flash.events.Event;
	import flash.text.TextField;
	import kizzo.datastruct.BinaryHeap;
	import kizzo.datastruct.HeapNode;
	

	public class Graph extends EventDispatcher
	{
		private var url_loader:URLLoader;		
		
		private var v_index_array:Array;
		private var v_name_array:Array;
		
		/**
		 * The sprite which the draw method uses to create a graphical representation of the graph.
		 */
		public var sprite:Sprite;
		
		/**
		 * Creates a directed, weighted graph.
		 */
		public function Graph() 
		{
			this.v_index_array = [];
			this.v_name_array = [];
			this.url_loader = new URLLoader();
		}
		
		/**
		 * Loads graph structure from an XML document.<br/>
		 * @param file_name The name of the xml file (including path).
		 * @example
		 * <listing>
		 * <br/>
		 * g = new Graph();
		 * g.loadXML("./xml/graph.xml");
		 * </listing>
		 * 
		 * Unnamed vertices will be given a name based on their index (which is internal) - V[index] (V0, V1, etc.).
		 * Edges that try to connect vertices that are already connected in the same direction will be omitted.
		 * The format for referring to unnamed vertces when defining an edge is #[index] (#0, #1, etc.).
		 * 
		 * Sample XML file content:
		 * <listing>
		 * <br/>
		 * &lt;?xml version="1.0" encoding="utf-8" ?&gt;	
		 * &lt;data&gt;		 
		 *		&lt;graph&gt;
		 *			&lt;vertices&gt;
		 *					&lt;vertex name="Plovdiv"/&gt;
		 *					&lt;vertex/&gt;
		 *			&lt;/vertices&gt;	
		 *			&lt;edges&gt;
		 *					&lt;edge from="Plovdiv" to="#1" weight="20"/&gt;
		 * 					&lt;edge from="#1" to="#0" weight="15"/&gt;
		 *			&lt;/edges&gt;
		 *		&lt;/graph&gt;
		 * &lt;/data>
		 * </listing>
		 */
		public function loadXML(file_name:String):void
		{			
			url_loader.load(new URLRequest(file_name));
			url_loader.addEventListener(Event.COMPLETE, process_xml);
		}
		
		
			
		
		
		private function process_xml(e:Event):void
		{
			var xml:XML = new XML(url_loader.data);
			
			var vertices:XMLList = xml.graph.vertices.children();
			var edges:XMLList = xml.graph.edges.children();
			
			for each (var vertex:XML in vertices)
			{				
				addVertex(new Vertex(this, String(vertex.@name)));
			}
			
			for each (var edge:XML in edges)
			{
				var from:String = edge.@from;
				var to:String = edge.@to;
				var weight:Number = Number (edge.@weight);
				
				var v_from:Vertex;
				var v_to:Vertex;
				
				if (from.charAt(0) == "#")									
					v_from = this.v_index_array[Number(from.slice(1))];
				else
					v_from = this.v_name_array[from];
				
				if (to.charAt(0) == "#")									
					v_to = this.v_index_array[Number(to.slice(1))];
				else
					v_to = this.v_name_array[to];					
					
				v_from.addEdge(new Edge(v_from, v_to, weight));
			}
			
			dispatchEvent(new Event(Event.COMPLETE));
		}
		
		
		
		/**
		 * Finds the shorthest path between two vertices
		 * If no such path exists the function returns null.
		 */
		public function findShortestPath(start_vertex:Vertex, end_vertex:Vertex):Path
		{
			reset_vertex_status();
			var priority_queue:BinaryHeap = new BinaryHeap();
			var current_vertex:Vertex;		
			var heap_node:HeapNode;
			
			var path:Path = new Path(start_vertex);
			priority_queue.addNode(path);
			
			while (priority_queue.length > 0 && current_vertex != end_vertex)
			{										
				heap_node = priority_queue.getNode();
				path = heap_node as Path;
				current_vertex = path.getLastVertex();
				var edge_iterator:ArrayIterator = current_vertex.getEdgeIterator();
				
				while (edge_iterator.hasNext())
				{											
					var e:Edge = edge_iterator.getNext();
					if (e.end_vertex.status == Vertex.NOT_VISITED)
					{	
						var path_copy:Path = path.clone();
						path_copy.add(e);
						priority_queue.addNode(path_copy);					
					}
				}				
				current_vertex.status = Vertex.VISITED;
			}
			
			if (path.getLastVertex() != end_vertex)
				path = null;
				
			return path;
		}
		
		
		
		/**
		 * Finds a random path between two vertices. If no such path exists, the function returns null.
		 */		
		public function findRandomPath(start_vertex:Vertex, end_vertex:Vertex):Path
		{
			reset_vertex_status();
			var queue:Array = [];
			var current_vertex:Vertex;					
			
			var path:Path = new Path(start_vertex);
			queue.push(path);
			
			while (queue.length > 0 && current_vertex != end_vertex)
			{										
				path = queue.shift() as Path;
				current_vertex = path.getLastVertex();
				var edge_iterator:ArrayIterator = current_vertex.getEdgeIterator();
				
				while (edge_iterator.hasNext())
				{											
					var e:Edge = edge_iterator.getNext();
					if (e.end_vertex.status == Vertex.NOT_VISITED)
					{
						var path_copy:Path = path.clone();
						path_copy.add(e);
						queue.splice(Math.floor(Math.random() * queue.length), 0, path_copy);
					}
				}				
				current_vertex.status = Vertex.VISITED;
			}
			
			if (path.getLastVertex() != end_vertex)
				path = null;
			return path;
		}
		
		
		
		private function reset_vertex_status():void
		{
			for (var i:uint = 0; i < this.v_index_array.length; i++)
			{
				v_index_array[i].status = Vertex.NOT_VISITED;
				v_index_array[i].path = null;
			}
		}
		
		
		
		/**
		 * Adds a vertex to the graph.
		 * If a vertex with the same name already exists it will not be added.
		 * If the vertex has no name, an automatically generated name will be assigned with the format V[index] (V0, V1 etc.)
		 */
		public function addVertex(v:Vertex):void
		{
			var name:String = v.name;
			
			if (this.v_name_array[name])
			{
				trace ("Duplicate vertex name. Vertex not added");
				return;
			}
			
			this.v_index_array.push(v);		
			
			if (name == "")
			{
				name = "V" + (this.v_index_array.length - 1);
				v.name = name;
			}
			this.v_name_array[name] = v;
		}
		
		
		
		/**
		 * The number of vertices the graph contains.
		 */
		public function get length():int
		{
			return this.v_index_array.length;
		}
		
		
		
		/**
		 * Adds an edge between two random vertices. The default weight range is 0-100. 
		 * Other values may be supplied as parameters.
		 */
		public function addRandomEdge(weight_low:Number=0, weight_high:Number=100):void
		{
			var from:Vertex = this.v_index_array[Math.round(Math.random() * (this.v_index_array.length - 1))];
			var to:Vertex = this.v_index_array[Math.round(Math.random() * (this.v_index_array.length - 1))];
			var weight:Number = weight_low + Math.round(Math.random()*(weight_high-weight_low));
			
			from.addEdge(new Edge(from, to, weight));
		}

		/**
		 * Creates an Edge from start_vertex to end_vertex.
		 * @param	weight - The weight of the edge. It must be non-negative.
		 */
		public function addEdge(start_vertex:Vertex, end_vertex:Vertex, weight:Number):void
		{
			start_vertex.addEdge(new Edge(start_vertex, end_vertex, weight));
		}		
		
		
		/**
		 * Display the graph in text format. The function uses trace, so traces must be visible (Debug build).
		 */
		public function traceGraph():void
		{			
			for (var i:uint = 0; i < this.v_index_array.length; i++)
			{				
				this.v_index_array[i].traceVertex();
			}
		}
			
		
		
		/**
		 * Draws the graph. The positions of its vertices and edges are random. 
		 * Once this method is used, the sprite property of the graph may be used to acess the graphic. 
		 * Each drawing creates a new sprite instance. The purpose of the graphic is to make debugging easier - you may reposition the vertices to make 
		 * the graphic more legible. A path consisting of vertices from a graph may be highlighted in the graph 
		 * with user defined or default ColorMatrixFilter.
		 * @see Path Path
		 */
		public function draw():void
		{
			sprite = new Sprite();			
			
			for (var i:uint = 0; i < this.v_index_array.length; i++)
			{
				this.v_index_array[i].draw();				
				//.x = this.v_index_array[i].pt.x;
				//.y = this.v_index_array[i].pt.y;
				sprite.addChild(this.v_index_array[i].sprite);				
			}

			/*for ( i = 0; i < this.v_index_array.length; i++)
			{,
				v_sprite = this.v_index_array[i].drawEdges();				
				v_sprite.x = this.v_index_array[i].pt.x;
				v_sprite.y = this.v_index_array[i].pt.y;
				sp.addChild(v_sprite);				
			}*/			
		}
		
		
		
		/**
		 * Returns the specified vertex.
		 * @param name The name of the vertex to be returned.
		 */
		public function getVertexByName(name:String):Vertex
		{
			return this.v_name_array[name];
		}
		
		
		
	}
	
}